package com.aqie.easy.stack;

import java.util.Stack;

/**
 * 844 含退格字符串
 */
public class BackspaceCompare {
    public boolean backspaceCompare(String S, String T) {
        if (S.length() == 0 && T.length() == 0) return true;
        return generate(S).equals(generate(T));
    }

    /**
     * 1, 3ms
     * @param str
     * @return
     */
    private String generate(String str){
        if (str.length() == 0) return "";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(c=='#'){
                if(sb.length()!=0) sb.deleteCharAt(sb.length()-1);
            }else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    /**
     * 2, 8ms
     * @param S
     * @return
     */
    private String generateString(String S) {
        Stack<Character> s = new Stack();
        for (Character s1 : S.toCharArray()){
            if (s1 == '#') {
               if (!s.empty()) s.pop();
            }
            else s.push(s1);
        }
        StringBuilder res = new StringBuilder();
        while (!s.empty()){
            res.append(s.pop());
        }
        return res.toString();
    }

}
